package com.xy6.algo.divide;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * 分治法求解凸包问题
 * 
 * <pre>
 * https://www.cnblogs.com/fei-er-blog/p/4827137.html
 * </pre>
 * 
 * @author zhang
 * @since 2018-05-23
 */
public class ConvexHull {

	public static void main(String[] args) {
		int[] x = { 1, 0, 1, 0 };
		int[] y = { 1, 0, 0, 1 };
		convexHull(x, y);
		System.out.println(calc(0, 0, 1, 1, 1, -2));
	}

	/**
	 * 分治法求解凸包问题，入口函数
	 * 
	 * @param x 点的x集合
	 * @param y 点的y集合
	 */
	public static int convexHull(int[] x, int[] y) {
		int len = x.length;
		Point[] points = new Point[len];
		for (int i = 0; i < len; i++) {
			points[i] = new Point(x[i], y[i]);
		}
		// 按x值排序
		points = sort(points);
		System.out.println(Arrays.toString(points));
		List<Integer> list = convexHull(points);
		for (Integer elem : list) {
			System.out.println(String.format("x:%d, y:%d", points[elem].x, points[elem].y));
		}
		return list.size();
	}

	/**
	 * 分治法解决凸包问题
	 * 
	 * @param points 目标点集（要求是按x坐标排好序的）
	 * @return 有序的极点集合
	 */
	private static List<Integer> convexHull(Point[] points) {
		List<Integer> indexs = new LinkedList<Integer>();
		for (int i = 0; i < points.length; i++) {
			indexs.add(i);
		}
		// 得到上包结果
		List<Integer> upperHull = upperHull(points, indexs);
		// 得到下包结果
		List<Integer> lowerHull = lowerHull(points, indexs);

		// 将上包结果、下包结果合并，并返回
		List<Integer> result = new LinkedList<Integer>();
		// 最左侧的点，一定是凸点
		result.add(indexs.get(0));
		for (int i = 0; i < upperHull.size(); i++) {
			result.add(upperHull.get(i));
		}
		// 最右侧的点，一定是凸点
		result.add(indexs.get(indexs.size() - 1));
		for (int i = 0; i < lowerHull.size(); i++) {
			result.add(lowerHull.get(i));
		}

		return result;
	}

	/**
	 * 分治法求解上包的凸点
	 * 
	 * @param points 所有点集合
	 * @param indexs 所有点的下标集合
	 * @return 上包的凸点
	 */
	private static List<Integer> lowerHull(Point[] points, List<Integer> indexs) {
		// 记录最大距离
		int dmin = 0;
		// 记录最大距离那点的下标
		Integer pmin = 0;
		// 分界向量起点
		Point p1 = points[indexs.get(0)];
		// 分界向量终点
		Point p2 = points[indexs.get(indexs.size() - 1)];
		System.out.println(String.format("lower line1: %d,%d - %d,%d ", p1.x, p1.y, p2.x, p2.y));

		// 位于分界向量左侧的点集下标
		List<Integer> newIndexs = new LinkedList<Integer>();
		for (int i = 1; i < indexs.size() - 1; i++) {
			int d = p1.x * p2.y + points[indexs.get(i)].x * p1.y + p2.x * points[indexs.get(i)].y
					- points[indexs.get(i)].x * p2.y - p2.x * p1.y - p1.x * points[indexs.get(i)].y;
			if (d < 0) {
				newIndexs.add(indexs.get(i));
				if (d < dmin) {
					dmin = d;
					pmin = indexs.get(i);
					System.out.println(String
							.format("lower dmin: %d, pmin:%d,%d", dmin, points[pmin].x, points[pmin].y));
				}
			}
		}
		if (dmin == 0) {
			System.out.println("lower no point");
			return new LinkedList<Integer>();
		}
		// 构建新目标点集序列
		List<Integer> newIndexs1 = new LinkedList<Integer>();
		List<Integer> newIndexs2 = new LinkedList<Integer>();
		newIndexs1.add(pmin);
		newIndexs2.add(indexs.get(0));
		System.out.println(String.format("lower line2: %d,%d - %d,%d ", points[indexs.get(0)].x,
				points[indexs.get(0)].y, points[pmin].x, points[pmin].y));
		for (Integer i : newIndexs) {
			newIndexs1.add(i);
			newIndexs2.add(i);
		}
		newIndexs1.add(indexs.get(indexs.size() - 1));
		newIndexs2.add(pmin);

		// 处理结果点集序列
		List<Integer> result1 = lowerHull(points, newIndexs1);
		System.out.println(String.format("lower result1: %s", result1.toString()));
		List<Integer> result2 = lowerHull(points, newIndexs2);
		System.out.println(String.format("lower result2: %s", result2.toString()));
		// 合并
		result1.add(pmin);
		for (Integer i : result2) {
			result1.add(i);
		}
		result2 = null;
		System.out.println(String.format("lower result: %s", result1.toString()));

		return result1;
	}

	/**
	 * 分治法求解下包问题
	 * 
	 * @param points
	 * @param indexs
	 * @return 返回有序的点击序列
	 */
	private static List<Integer> upperHull(Point[] points, List<Integer> indexs) {
		// 记录最大距离
		int dmax = 0;
		// 记录最大距离那点的下标
		Integer pmax = 0;
		// 分界向量起点
		Point p1 = points[indexs.get(0)];
		// 分界向量终点
		Point p2 = points[indexs.get(indexs.size() - 1)];
		System.out.println(String.format("upper line1: %d,%d - %d,%d ", p1.x, p1.y, p2.x, p2.y));

		List<Integer> newIndexs = new LinkedList<Integer>();
		for (int i = 1; i < indexs.size() - 1; i++) {
			int d = p1.x * p2.y + points[indexs.get(i)].x * p1.y + p2.x * points[indexs.get(i)].y
					- points[indexs.get(i)].x * p2.y - p2.x * p1.y - p1.x * points[indexs.get(i)].y;
			if (d > 0) {
				newIndexs.add(indexs.get(i));
				if (d > dmax) {
					dmax = d;
					pmax = indexs.get(i);
					System.out.println(String
							.format("upper dmin: %d, pmin:%d,%d", dmax, points[pmax].x, points[pmax].y));
				}
			}
		}
		if (dmax == 0) {
			System.out.println("upper no point");
			return new LinkedList<Integer>();
		}
		List<Integer> newIndexs1 = new LinkedList<Integer>();
		List<Integer> newIndexs2 = new LinkedList<Integer>();
		newIndexs1.add(indexs.get(0));
		newIndexs2.add(pmax);
		System.out.println(String.format("upper line2: %d,%d - %d,%d ", points[indexs.get(0)].x,
				points[indexs.get(0)].y, points[pmax].x, points[pmax].y));
		for (Integer i : newIndexs) {
			newIndexs1.add(i);
			newIndexs2.add(i);
		}
		newIndexs1.add(pmax);
		newIndexs2.add(indexs.get(indexs.size() - 1));

		// 处理结果点集序列
		List<Integer> result1 = upperHull(points, newIndexs1);
		System.out.println(String.format("upper result1: %s", result1.toString()));
		List<Integer> result2 = upperHull(points, newIndexs2);
		System.out.println(String.format("upper result2: %s", result2.toString()));
		result1.add(pmax);
		for (Integer i : result2) {
			result1.add(i);
		}
		result2 = null;
		System.out.println(String.format("upper result1: %s", result1.toString()));

		return result1;
	}

	private static class Point {
		private int x;
		private int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}
	}

	/**
	 * 对点集按x升序排列。 此处使用jdk提供的排序算法，未自己实现
	 * 
	 * @param points
	 */
	private static Point[] sort(Point[] points) {
		List<Point> list = Arrays.asList(points);
		Collections.sort(list, new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				return o1.x == o2.x ? 0 : (o1.x < o2.x ? -1 : 1);
			}
		});
		list.toArray(points);
		return points;
	}

	/**
	 * 计算点到直线的截距
	 * <p>
	 * 根据两点确认一条直线，得到一次项表达式，将第三个点代入表达式得到截距
	 * 
	 * <pre>
	 * 正数，点在直线上方
	 * 0，点在直线上
	 * 负数，点在直线下方
	 * </pre>
	 * 
	 * @param x1
	 * @param y1
	 * @param x2
	 * @param y2
	 * @param x3
	 * @param y3
	 * @return
	 */
	private static int calc(int x1, int y1, int x2, int y2, int x3, int y3) {
		if (x1 == x2) {
			return x3 - x1;
		}
		return (y1 - y2) * x3 - (x1 - x2) * y3 + (x1 * y2 - x2 * y1);
	}

}
